package com.biao.collection;

public class LinkedList {
    /*
    LinkedList原理 底层基于链表结构

      数组与链表结构区别：
      数组：保证元素有序性 可以基于下标查询时间复杂度:o（1）
      链表：单向链表和双向链表 可以基于下标查询 时间复杂度:o（n）

      数组适合于： 基于下标查询 增删有可能会对我们数组实现移动，效率非常低；
      链表适合于： 增删 只需要该引用指针关系

      HashMap底层单链表
、
      LinkedList底层双向链表
      HashMap底层单链表 不能保证key有序性
      LinkedHashMap双向链表 保证key有序性

      LinkedList为什么需要用一个变量记录下头结点 后期遍历数据知道从哪里开始

      链表的index值是怎么知道的呢？  链表长度
     */

    private static class Node<E> {
        E item;
        Node<E> next;   // 链表下个元素
        Node<E> prev;   // 链表上个元素

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
    // 第一个节点
//    transient Node<E> first;
    // 最后一个节点
//    transient Node<E> last;

    // 添加元素逻辑
    /*
    public boolean add(E e) {   // 添加元素调用 linkLast 方法
        linkLast(e);
        return true;
    }

    void linkLast(E e) {
        final Node<E> l = last;     // 拿到最后一个节点
        final Node<E> newNode = new Node<>(l, e, null); // 要添加的节点赋值
        last = newNode; // 要添加的元素变成最后一个节点，记录方便下次进入方法后使用
        if (l == null)  // 最后一个节点为空
            first = newNode;    // 添加的节点就是第一个
        else
            l.next = newNode;   // 添加到链表末尾
        size++;
        modCount++;
    }
     */

    // get 方法逻辑
    /*
    public E get(int index) {
        checkElementIndex(index);   // 验证下标值是否正确
        return node(index).item;    // 调用
    }

    Node<E> node(int index) {   // 获取元素方法
        // assert isElementIndex(index);

        // size右移1位，等于/2了，等于取到了下标的中间值，二分查找
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++) // 循环前半段链表遍历到index位置
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)  // 从后往前遍历查找要找index下标的元素
                x = x.prev;
            return x;
        }
    }
     */

    // remove 方法
    /*
    public boolean remove(Object o) {
        if (o == null) {    // 判断删除值为null的元素
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {   // 整个循环一遍，遇到元素为空的就删除
                    unlink(x);  // 执行删除
                    return true;
                }
            }
        } else {    // 要删除的这个元素，值不是null
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {     // 整个遍历一遍，元素的值就是要删除的元素
                    unlink(x);  // 执行删除
                    return true;
                }
            }
        }
        return false;
    }

    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;    // 链表上的下个节点
        final Node<E> prev = x.prev;    // 链表上的前面一个节点

        if (prev == null) { // 判断是否是头节点：前一个节点为空，说明到达了最前面了，说明要删除的这个节点就是第一个节点
            first = next;   // 后面的那个节点变成了第一个节点
        } else {
            prev.next = next;   // 要删除这个元素的后面一个节点和前一个节点关联，使用指针指向
            x.prev = null;      // 要删除的这个节点，指向前面那个节点的指向置空
        }

        if (next == null) {     // 后面一个节点为空，说明要删除的这个节点就是尾节点
            last = prev;    // 前面的一个节点就变成了尾节点
        } else {
            next.prev = prev;   // 下一个节点的指向上一个节点的指向，变成了上一个节点，当前要删除的节点没有指向了
            x.next = null;      // 要删除节点的下一节点的指向置空
        }

        x.item = null;      // 要删除的节点置空了，删除了
        size--;         // 集合大小-1
        modCount++;
        return element;
    }
     */
}
